Due to an increase in the amount of online business transactions, efficiency in the query processing of large amounts of data stored in databases, data warehouses, and other information systems, has become increasingly important. Since the late 1970s, research and development activities have persisted throughout academia and industry in studying efficient query processing operations in standalone databases, distributed databases, hierarchical databases, spatial databases, and databases on the World Wide Web. Comprehensive reviews of reported query processing techniques have been provided in several sources, see, e.g., G. Graefe, “Query Evaluation Techniques for Large Databases,” ACM Computing Surveys, Volume 25 Issue 2, June 1993; and D. Kossmann, “The State of the Art in Distributed Query Processing,” ACM Computing Surveys, Volume 32 Issue 4, December 2000.
Database query processing operations typically consist of six phases: parsing, semantic checking, query rewrite, plan optimization, plan refinement, and query evaluation. The reasons for rewriting a query in query processing operations have been described in several references, see, e.g., L. M. Haas et al., “Extensible Query Processing in Starburst,” ACM SIGMOD Record, Volume 18 Issue 2, June 1989. Some reasons for query rewrite include:
1. Alternative phrasing of a query: Since relational query languages are nonprocedural, the alternatives perform equivalently; and
2. Involvement of view abstractions in a query: Since view definitions are hidden from the query writer, a query involving views can only be expanded by the database.
Traditional query rewrite strategies focus on rewrite and optimization for attributes that appear in query predicates, see, e.g., G. Graefe et al., “Dynamic Query Evaluation Plans,” ACM SIGMOD Record, Volume 18 Issue 2, June 1989; and D. Kossmann et al., “Iterative Dynamic Programming: A New Class of Query Optimization Algorithms,” ACM Transactions on Database Systems, Volume 25 Issue 1, March 2000.